Redução polinomial e NP-completude

Como já foi dito, há muitos problemas de computação com aplicações práticas importantes para os quais não conhecemos algoritmos eficientes. Isto posto, uma ideia é investigar a complexidade relativa dos problemas em \mathtt{NP}. Um problema \mathcal A não é mais difícil que um problema \mathcal B se uma solução para \mathcal B implica numa solução para \mathcal A com perda de desempenho polinomial relativa a eficiência da solução de \mathcal B. Façamos isso mais preciso.

Se {\mathcal A} e {\mathcal B} são problemas computacionais de decisão então uma redução em tempo polinomial de {\mathcal A} para {\mathcal B} é um algoritmo eficiente {M} que computa uma função {M : \mathcal I(\mathcal{A}) \rightarrow \mathcal I(\mathcal{B})} tal que para todo instância {I\in\mathcal I(\mathcal A)} de {\mathcal A} a instância {M(I)\in\mathcal I(\mathcal B)} do problema {\mathcal B} têm a mesma resposta.

Escrevemos {\mathcal A \leq_p \mathcal B}.

Notemos que se há uma redução de {\mathcal A} para {\mathcal B} e {M_B} é um algoritmo que resolve {\mathcal B} então o seguinte algoritmo resolve {\mathcal A}

{ M_A(I)}

 Devolva { M_B\big( M(I) \big)}.

ademais, se {M_B} é um algoritmo de tempo {t(n)} e {M} é um algoritmo de tempo {p(n)} então {M_A} acima tem consumo de tempo {t(p(n))}, que é um polinômio sempre que {t} for um polinômio. Notemos que {|\langle M(I) \rangle| = O(p(|\langle I \rangle|))}, ou seja, a saída de {M} tem tamanho polinomial no tamanho de {I}. Com isso temos

Teorema 5 Se {\mathcal A\leq_p \mathcal B} e {\mathcal B \in \mathtt{P}} então {\mathcal A \in \mathtt{P}}.

Teorema 6 {\textsc{hamiltoniano} \leq_p \textsc{tsp}}.

Demonstração: Seja {G=(V,A)} uma instância de {\textsc{hamiltoniano}}. Considere o algoritmo que com entrada {G} constrói o grafo {K=(V,A')} completo sobre {V}, constrói a função peso {\rho : A \rightarrow \{1,2\}} dada por

\displaystyle \rho ( \{x,y\} )= \begin{cases} 1, & \text{ se } \{x,y\}\in A\\ 2, & \text{ se } \{x,y\}\not\in A \end{cases}

e toma {k=|V|}.

Se {G} é dado pela matriz de adjacências, {\rho} é uma matriz obtida da matriz de {G} trocando {0} por {2}. O grafo {H} também e dado por uma matriz da mesma ordem. Assim, a descrição {\langle H,\rho,k \rangle} é obtida em tempo linear de {\langle G \rangle}.

Ainda, se {G} tem um circuito hamiltoniano então {H} tem um circuito hamiltoniano de peso {k}. Se {G} não tem um circuito hamiltoniano então todo circuito hamiltoniano de {H} tem peso {\geq k+1}. \Box

Um clique num grafo {G} é um subconjunto de vértices que induz um subgrafo completo, isto é, todos os pares de vértices desse subconjunto são arestas no grafo. {\textsc{clique}} é o problema: dado um grafo {G} e um inteiro {k>0} decidir se {G} tem um clique com pelo menos {k} vértices.

Uma cobertura num grafo {G} é um subconjunto {C} de vértices de {G} tal que qualquer aresta de {G} tem pelo menos um vértice em {C}. {\textsc{cobertura}} é o problema: dado um grafo {G} é um inteiro {k>0} decidir se {G} tem uma cobertura com no máximo {k} vértices.

Teorema 7 {\textsc{clique} \leq_p \textsc{v\'ertice-cobertura}}.

Demonstração: Dada uma instância {(G,k)} de {\textsc{clique}} o algoritmo {M} constrói em tempo linear {\overline G} e toma {|V|-k} para a instância {(\overline G , |V|-k)} de {\textsc{v\'ertice-cobertura}}. . Seja {C} um clique com {\geq k} vértices em {G}. Então para toda aresta {\{x,y\}} em {\overline G} temos que como {C} é independente em {\overline G} no máximo um dentre {x} e {y} está em {C} de modo que {V-C} é uma cobertura em {\overline G} com {|V|-|C| \leq |V| - k} vértices.

Por outro lado, se {D} é uma cobertura com no máximo {|V|-k} vértices em {\overline G}, então {V-D} é independente em {\overline G}, portanto, um clique com {\geq k} vértices em {G} \Box

Uma fórmula booleana satisfazível está em {\textsc{3sat}} se todas as suas cláusulas têm exatamente 3 literais.

Teorema 8 {\textsc{sat} \leq_p \textsc{3sat}}.

Demonstração: Seja {\Phi=(X,C)} uma instância de {\textsc{sat}}. Vamos descrever a construção de uma instância {\Phi^{(3)}=(X^{(3)},C^{(3)})} de {\textsc{3sat}}.

Seja {C_i \in C} uma cláusula de {\Phi}. A construção de {\Phi^{(3)}} considera 4 casos de acordo com o número de literais da cláusula: {1}, {2} {3} e {\geq 4}

Se {|C_i|=1}, digamos que {C_i = \ell_{i_1}}, então criamos a variáveis {X_i^{(3)} = \{y_{i_2}, y_{i_3} \}} e escrevemos

\displaystyle C_i^{(3)} := \bigg\{ \{ \ell_{i_1} , y_{i_2}, y_{i_3}\} , \{ \ell_{i_1} , \overline {y_{i_2}}, y_{i_3}\} , \{ \ell_{i_1} , y_{i_2}, \overline{ y_{i_3}}\},\{ \ell_{i_1} , \overline{y_{i_2}}, \overline{y_{i_3}}\} \bigg\}

que corresponde à fórmula

\displaystyle (\ell_{i_1} \vee y_{i_2} \vee y_{i_3}) \wedge (\ell_{i_1} \vee \overline {y_{i_2}} \vee y_{i_3}) \wedge (\ell_{i_1} \vee y_{i_2} \vee \overline { y_{i_3}}) \wedge (\ell_{i_1} \vee \overline {y_{i_2}} \vee \overline {y_{i_3}}) \ \ \ \ \ (4)

 

Dessa forma, qualquer atribuição que faça { C_i^{(3)} } verdadeira, faz { C_i } verdadeira e qualquer extensão de uma atribuição que faça { C_i} faz { C_i^{(3)} } verdadeira.

Se {|C_i|=2}, digamos que {C_i =\{ \ell_{i_1}, \ell_{i_2}\}}, então criamos a variáveis {X_i^{(3)} = \{y_{i_3} \}} e escrevemos

\displaystyle C_i^{(3)} := \bigg\{ \{ \ell_{i_1} , \ell_{i_2}, y_{i_3}\} , \{ \ell_{i_1} , \ell_{i_2}, \overline{ y_{i_3}}\}\bigg\}

que corresponde à fórmula

\displaystyle (\ell_{i_1} \vee \ell_{i_2} \vee y_{i_3}) \wedge (\ell_{i_1} \vee \ell_{i_2} \vee \overline { y_{i_3}}) \ \ \ \ \ (5)

 

Dessa forma, qualquer atribuição que faça { C_i^{(3)} } verdadeira, faz { C_i } verdadeira e qualquer extensão de uma atribuição que faça { C_i} faz { C_i^{(3)} } verdadeira.

Se {|C_1|= 3} então {X_i^{(3)} =\emptyset} e { C_i^{(3)} = C_i}.

Finalmente, se {|C_1| = p > 3}, digamos que {C_i = \{\ell_{i_1}, \ell_{i_2}, \dots , \ell_{i_p} \}}, então criamos as {p-3} variáveis {X_i^{(3)} = \{y_{i_1}, \dots, y_{i_{p-3}} \}} e fazemos { C_i^{(3)} } da seguinte forma

\displaystyle \begin{array}{rcl} C_i^{(3)} =&\big\{ \{\ell_{i_1},\ell_{i_2},y_{i_1}\}, \\ &\{\overline{y_{i_1}},y_{i_2},\ell_{i_3}\}, \\ &\{\overline{y_{i_2}},y_{i_3},\ell_{i_4}\}, \\ &\{\overline{y_{i_3}},y_{i_4},\ell_{i_5}\}, \\ &\vdots \\ &\{\overline{y_{i_{p-3}}},\ell_{i_{p-1}},\ell_{i_p}\}\big\}. \end{array}

e fica como exercício verificar que se { C_i} é satisfazível se, e só se, { C_i^{(3)}} é satisfazível. Com isso, a fórmula {\Phi^{(3)}} é dada pelas variáveis {X \cup (\bigcup_i X_i^{(3)})} e pelas cláusualas {\bigcup_i C_i^{(3)}.}.

Resta mostrar que essa construção pode ser feita em tempo polinomial no tamanho da descrição de {\Phi}.\Box

\textsc{clique} é a linguagem definida pelo problema de decisão: Dado um grafo {G} e um natural {k} decidir se {G} contém um clique com {\geq k} vértices.

Teorema 9 {\textsc{3sat} \leq_p \textsc{clique}}.

Demonstração: Seja {\Phi = (X,C)} uma instância de {\textsc{sat}} e vamos construir uma instância {(G, |C|)} de {\textsc{clique}}.

Se {\Phi} tem cláusulas {C_1,C_2,\dots,C_k} então {G} tem {3k} vértices denotados {v_{i,j}}, para {1\leq i \leq k} e {1\leq j \leq 3}. O vértice {v_{i,j}} corresponde ao literal {j} da cláusula {i}, denotado {\ell_{i,j}}. As arestas são dadas pelos pares de vértices

\displaystyle \{ v_{i,j} ,v_{k,l}\}

com {i\neq k} (correspondem a cláusulas diferentes) e cujos literais podem ser simultaneamente verdadeiros (não contraditórios). Notemos que {C_i= \{\ell_{i,1}, \ell_{i,2},\ell_{i,3}\}} corresponde a um conjunto independente {\{v_{i_1}, v_{i_2},v_{i_3}\}} em {G}.

satclique

Seja {t} uma atribuição que satisfaz todas as cláusulas de {\Phi} e sejam {\ell_{1,j_1},\dots,\ell_{k,j_k}} um literal com valor {\textsc{verdadeiro}} de cada cláusula. Então {v_{1,j_1},v_{2,j_j},\dots,v_{k,j_k}} é um clique com {k}-vértices em {G}.

Agora, suponha que {G} tem um clique com pelo menos {k} vértices. Seja {U} um subconjunto de vértices de cardinalidade {k} que define um clique em {G}. Como vértices da mesma cláusula não são adjacentes, devemos ter um vértice correspondente a cada cláusula de {\Phi}. Definimos a seguinte atribuição na variáveis de {\Phi}: se {x} é uma variável que corresponde a um vértice de {U} então {t(x)} é verdadeiro, caso contrário, {t(x)} é falso. Assim {t} satisfaz todas as cláusulas.

Resta mostrar que essa construção pode ser feita em tempo polinomial no tamanho da descrição de {\Phi}. Basta notar que {G} tem {3k} vértices portanto construímos uma matriz de tamanho {9k^2} que é polinomial no tamanho da representação de {\Phi}. \Box

Exercício 5 {\textsc{conjunto-independente}} é o problema: Dado um grafo {G} e um natural {k} decidir se {G} contém um conjunto independente com {\geq k} vértices. Prove que {\textsc{3sat} \leq_p \textsc{conjunto-independente}}.

— NP-completude —

Um problema {\mathcal A} é {\mathtt{NP}}-difícil se todos os problemas em {\mathtt{NP}} não são mais difíceis do que {\mathcal A} no seguinte sentido:

\displaystyle \mathcal B \leq_p \mathcal A \text{ para todo }\mathcal B \in \mathtt{NP}. \ \ \ \ \ (6)

 

Suponhamos que {\mathcal A} tenha um algoritmo {M_{\mathcal A}} que o resolve em tempo {O(n^t)} e seja {M} a redução de {\mathcal B\in\mathtt{NP}} para {\mathcal A} que consome tempo {O(n^k)} para algum natural {k}. Então, se {I} é uma instância de tamanho {n} para {\mathcal B}, {M(I)} é uma instância de tamanho {O(n^k)} para {\mathcal A} cuja resposta {M_{\mathcal A}( M(I))} é computada em tempo {O( (n^k)^t )}. Portanto,

Teorema 11 Se algum problema {\mathtt{NP}}-difícil tem algoritmo eficiente, todos os problemas em {\mathtt{NP}} têm algoritmo eficiente, isto é, {\mathtt{P}=\mathtt{NP}}.

Um problema é {\mathcal A} {\mathtt{NP}}-completo se

  1. {\mathcal A\in \mathtt{NP}},
  2. {\mathcal A} é {\mathtt{NP}}-difícil.

Como consequência dessa definição e da proposição acima

Corolário 12 Se algum problema {\mathtt{NP}}-completo tem algoritmo eficiente então {\mathtt{P}=\mathtt{NP}}.

Proposição 13 Se algum problema {\mathtt{NP}}-completo não tem algoritmo eficiente então nenhum outro problema {\mathtt{NP}}-completo tem, isto é {\mathtt{P}\cap \mathtt{NP-completo}=\emptyset}.

Demonstração: Exercício. \Box

Proposição 14 Se {\mathcal A} é {\mathtt{NP}}-completo e {\mathcal A\leq_p \mathcal B} então {\mathcal B} é {\mathtt{NP}}-difícil.

Demonstração: Exercício. \Box

Teorema 15 (Cook e Levin, 1970) {\textsc{sat}} é {\mathtt{NP}}-completo.

Corolário 16 {\textsc{3sat}} é {\mathtt{NP}}-completo.

Demonstração: Vimos que {\textsc{sat} \leq_p \textsc{3sat}}, portanto, {\textsc{3sat}} é {\mathtt{NP}}-difícil. Claramente, {\textsc{3sat}} está em {\mathtt{NP}} (por quê?). \Box

Corolário 17 {\textsc{clique}} é {\mathtt{NP}}-completo.

Demonstração: Vimos que {\textsc{3sat} \leq_p \textsc{clique}}, portanto, {\textsc{3sat}} é {\mathtt{NP}}-difícil. Fica como exercício para o leitor verificar que {\textsc{clique}} está em {\mathtt{NP}}. \Box

Corolário 18 {\textsc{v\'ertice-cobertura}} é {\mathtt{NP}}-completo.

Demonstração: Vimos que {\textsc{clique} \leq_p \textsc{v\'ertice-cobertura}}, portanto, {\textsc{v\'ertice-cobertura}} é {\mathtt{NP}}-difícil. Fica como exercício para o leitor verificar que {\textsc{v\'ertice-cobertura}} está em {\mathtt{NP}}. \Box

Além desses, dos outros problemas citados nestas notas, é sabido que {\textsc{hamiltoniano}} é {\mathtt{NP}}-completo e que {\textsc{tsp}} é {\mathtt{NP}}-completo. Uma curiosidade: em maio de 2004, o problema caixeiro-viajante nas 24.978 cidades da Suécia foi resolvido (veja aqui).

Há muitos problemas {\mathtt{NP}}-completos. São tantos e tão pesquisados que muitos pesquisadores acreditam que {\mathtt{P}\neq \mathtt{NP}} simplesmente porque se houvesse um algoritmo eficiente para algum desses problemas ele certamente já teria sido descoberto. Veja aqui uma lista de problemas {\mathtt{NP}}-completos.

Screenshot from 2016-04-27 10:03:28

 

Deixe um comentário